package com.leetcode.动态规划;

/**
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * @author LZF
 *
 */
public class L718最长重复子数组 {	
	public static void main(String[] args) {
		int result = findLength(new int[] {1,2,3,2,1}, new int[] {3,2,1,4,7});
		System.out.println(result);
	}

	/**
	 * dp[i][j]:A以i为结尾，B以j为结尾的最长公共子序列的长度。
	 * dp[i][j]有两种情况而来：
	 * 一、A[i] == B[j]，则dp[i][j] = dp[i - 1][j - 1] + 1，
	 * 二、A[i] != B[j]，则dp[i][j] = 0，因为题目要求连续，根据我们定义dp的含义，
	 * 如果A[i] != B[j]，那A以i为结尾，B以j为结尾的最长公共子序列的长度就为0
	 * 
	 * 初始化
	 * if(i == 0 || j == 0) dp[i][j] = (A[i] == B[j]) ? 1 : 0 ,（最多也只有一个元素相等）
	 * 
	 * 返回：
	 * 由于dp[i][j]的定义是A以i为结尾，B以j为结尾的最长公共子序列的长度，
	 * dp[i][j]并不一定受dp[i-1][j-1]的影响，因此返回dp数组中最大的才是正确的答案。
	 */
	public static int findLength(int[] nums1, int[] nums2) {
		int[][] dp = new int[nums1.length][nums2.length];
		int result = 0;
		for(int i = 0;i < nums1.length;i++) {
			for(int j = 0;j < nums2.length;j++) {
				if(i == 0 || j == 0)
					dp[i][j] = (nums1[i] == nums2[j]) ? 1 : 0;
				else 
					dp[i][j] = (nums1[i] == nums2[j]) ? dp[i - 1][j - 1] + 1 : 0;
				result = Math.max(result, dp[i][j]);
			}
		}
		return result;
    }
	
	/**
	 * 升级：dp数组可以变为一维dp
	 */
}
